#pragma once
#include<iostream>
#include<vector>
using namespace std;


template<class T>
struct my_hash
{
    size_t operator() (const T& x) const
    {
        return (size_t)x;
    }
};
template<>
struct my_hash<string>
{
    size_t operator() (const string& x) const
    {
        size_t res = 0, p = 1;
        for(auto& c : x)
        {
            res += p * c;
            p *= 131;
        }
        return res;
    }
};

// 哈希表的节点（单链表）
template<class T>
struct hash_table_node
{
    T _val;
    hash_table_node* _next;

    hash_table_node(const T& x = T(), hash_table_node* next = nullptr)
        :_val(x)
        ,_next(next)
    {}
};

template<class K, class T, class K_of_T, class Hash = my_hash<T>>
class HashTable;

template<class T, class K_of_T, class Hash>
struct HashTable_iterator
{
    typedef hash_table_node<T> node;
    typedef HashTable_iterator<T, K_of_T, Hash> Self;

    node* _pnode;
    vector<node*>* _ph;

    HashTable_iterator(node* pnode = nullptr, vector<node*>* ph = nullptr)
        :_pnode(pnode)
        ,_ph(ph)
    {}

    Self& operator++ ()
    {
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else
        {
            Hash get_hash;
            K_of_T get_key;
            int pos = get_hash(get_key(_pnode->_val)) % _ph->size();
            pos++;
            while(pos < _ph->size() && !(*_ph)[pos])
                ++pos;
            if(pos < _ph->size())
                _pnode = (*_ph)[pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    bool operator!= (const Self& it) const
    {
        return _pnode != it._pnode;
    }
    T& operator* () { return _pnode->_val; }
    T* operator-> () { return &_pnode->_val; }
};

// 哈希表
// template<class T, class Hash = my_hash<T>>
template<class K, class T, class K_of_T, class Hash>
class HashTable
{
public:
    typedef hash_table_node<T> node;
private:
    vector<node*> _h;   // 链表数组
    int _size = 0;      // 表中的元素个数

public:
    HashTable(int n = 10)
        :_h(n)
    {}
    size_t size() { return _size; }
    bool empty() { return !_size; }
    typedef HashTable_iterator<T, K_of_T, Hash> iterator;
    iterator begin()
    {
        if(empty()) return {nullptr, nullptr};
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return {_h[i], &_h};
        return {nullptr, nullptr};
    }
    iterator end() { return {nullptr, &_h}; }

    iterator find(const K& key)
    {
        // 求存储位置时加上get_key
        Hash get_hash;
        K_of_T get_key;
        int pos = get_hash(key) % _h.size();
        for(node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key)
                return {i, &_h};
        return {nullptr, &_h}; // 未找到返回空
    }
    iterator insert(const T& x)
    {
        Hash get_hash;
        K_of_T get_key;
        // 表中已经有x了，无需重复插入
        iterator p = find(get_key(x));
        if(p._pnode) return p;

        // 引入负载因子，适当扩容
        if(_size >= 0.7 * _h.size())
        {
            vector<node*> new_h(2 * _h.size()); // 按2倍扩容
            for(int i = 0; i < _h.size(); i++)
            {
                if(_h[i])
                {
                    node* j = _h[i];
                    while(j)
                    {
                        // 求存储位置时加上get_key
                        int pos = get_hash(get_key(j->_val)) % new_h.size();
                        node* next = j->_next;
                        j->_next = new_h[pos];  // 这里直接把旧表中的节点移动到新表中
                        new_h[pos] = j;
                        j = next;
                    }
                }
            }
            _h.swap(new_h);
        }
        // 求存储位置时加上get_key
        int pos = get_hash(get_key(x)) % _h.size();
        // 头插
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {cur, &_h};
    }

    bool erase(const K& key)
    {
        Hash get_hash;
        K_of_T get_key;

        // 求存储位置时加上get_key
        int pos = get_hash(key) % _h.size();   
        for(node* i = _h[pos], *pre = nullptr; i; i = i->_next)
        {
            if(get_key(i->_val) == key)
            {
                if(!pre)
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }
};